package class03;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 使用两个队列实现栈功能
 * 
 * 算法原理：
 * 栈的特点是后进先出(LIFO)，而队列的特点是先进先出(FIFO)。
 * 通过两个队列的配合使用，可以实现栈的功能：
 * 1. queue：主队列，用于存储栈中的元素
 * 2. help：辅助队列，用于临时存储元素
 * 
 * 核心思想：
 * 在执行pop或peek操作时，将主队列中除最后一个元素外的所有元素转移到辅助队列，
 * 最后一个元素就是要获取的栈顶元素，然后交换两个队列的角色。
 * 
 * 时间复杂度分析：
 * - push操作：O(1)
 * - pop和peek操作：O(N)，其中N为栈中元素个数
 * 
 * 空间复杂度：O(N)，其中N为栈中的元素个数
 */
public class Code07_TwoQueueImplementStack {

	/**
	 * 双队列实现栈的数据结构
	 * 
	 * 设计思路：
	 * - queue：主队列，用于存储栈中的元素
	 * - help：辅助队列，主要用于临时存储元素
	 * 
	 * 数据转移策略：
	 * 在pop/peek操作时，将queue中除最后一个元素外的所有元素转移到help队列，
	 * 最后一个元素就是栈顶元素，操作完成后交换两个队列的角色。
	 * 
	 * @param <T> 栈中元素的类型
	 */
	public static class TwoQueueStack<T> {
		public Queue<T> queue; // 主队列，用于存储栈中的元素
		public Queue<T> help;  // 辅助队列，用于临时存储元素

		/**
		 * 构造函数，初始化两个队列
		 */
		public TwoQueueStack() {
			queue = new LinkedList<>(); // 主队列
			help = new LinkedList<>();  // 辅助队列
		}

		/**
		 * 向栈顶压入元素（入栈操作）
		 * 时间复杂度：O(1)
		 * 
		 * @param value 要压入栈的元素
		 */
		public void push(T value) {
			// 直接将元素添加到主队列末尾
			queue.offer(value);
		}

		/**
		 * 弹出栈顶元素（出栈操作）
		 * 时间复杂度：O(N)，其中N为栈中元素个数
		 * 
		 * 实现原理：
		 * 1. 将主队列中除最后一个元素外的所有元素转移到辅助队列
		 * 2. 主队列中剩下的最后一个元素就是栈顶元素
		 * 3. 弹出该元素作为返回值
		 * 4. 交换主队列和辅助队列的角色
		 * 
		 * @return 栈顶元素
		 */
		public T poll() {
			// 将主队列中除最后一个元素外的所有元素转移到辅助队列
			while (queue.size() > 1) {
				help.offer(queue.poll());
			}
			T ans = queue.poll(); // 获取栈顶元素
			// 交换主队列和辅助队列的角色
			Queue<T> tmp = queue;
			queue = help;
			help = tmp;
			return ans; // 返回栈顶元素
		}

		/**
		 * 查看栈顶元素但不弹出
		 * 时间复杂度：O(N)，其中N为栈中元素个数
		 * 
		 * 实现原理：
		 * 1. 将主队列中除最后一个元素外的所有元素转移到辅助队列
		 * 2. 主队列中剩下的最后一个元素就是栈顶元素
		 * 3. 记录该元素并将其也转移到辅助队列（因为是查看而非弹出）
		 * 4. 交换主队列和辅助队列的角色
		 * 
		 * @return 栈顶元素
		 */
		public T peek() {
			// 将主队列中除最后一个元素外的所有元素转移到辅助队列
			while (queue.size() > 1) {
				help.offer(queue.poll());
			}
			T ans = queue.poll(); // 获取栈顶元素
			help.offer(ans); // 将栈顶元素也转移到辅助队列（因为是查看而非弹出）
			// 交换主队列和辅助队列的角色
			Queue<T> tmp = queue;
			queue = help;
			help = tmp;
			return ans; // 返回栈顶元素
		}

		/**
		 * 判断栈是否为空
		 * 时间复杂度：O(1)
		 * 
		 * @return 如果栈为空返回true，否则返回false
		 */
		public boolean isEmpty() {
			// 只需要判断主队列是否为空即可
			return queue.isEmpty();
		}

	}

	public static void main(String[] args) {
		System.out.println("test begin");
		TwoQueueStack<Integer> myStack = new TwoQueueStack<>();
		Stack<Integer> test = new Stack<>();
		int testTime = 1000000;
		int max = 1000000;
		for (int i = 0; i < testTime; i++) {
			if (myStack.isEmpty()) {
				if (!test.isEmpty()) {
					System.out.println("Oops");
				}
				int num = (int) (Math.random() * max);
				myStack.push(num);
				test.push(num);
			} else {
				if (Math.random() < 0.25) {
					int num = (int) (Math.random() * max);
					myStack.push(num);
					test.push(num);
				} else if (Math.random() < 0.5) {
					if (!myStack.peek().equals(test.peek())) {
						System.out.println("Oops");
					}
				} else if (Math.random() < 0.75) {
					if (!myStack.poll().equals(test.pop())) {
						System.out.println("Oops");
					}
				} else {
					if (myStack.isEmpty() != test.isEmpty()) {
						System.out.println("Oops");
					}
				}
			}
		}

		System.out.println("test finish!");

	}

}